오일러 정리

레온하르트 오일러가 증명한 정리이다.

정수론에서 유용하게 쓰이는 정리로, 합동식과 관련이 있다. 페르마의 소정리를 일반화한 것이다.
내용은 아래와 같다.

여기서 $\varphi \left( n \right)$은 $1$부터 $n$까지의 정수 중 $n$과 서로소인 정수의 개수를 구하는 오일러 파이 함수다.

$n$ 이하의 자연수중 $n$과 서로소인 수만 모아놓은 집합을 $S$라 하자.
정의에 의해 $S$의 원소의 개수는 $\varphi \left( n \right)$이다.

$S=\left\{b_1, \cdots, b_{\varphi\left(n\right)}\right\}$

라 하자

$S$의 각 원소들에 ($n$과 서로소인) $a$를 곱한 집합을 $aS$라 하면
$aS=\left\{ab_1, \cdots, ab_{\varphi\left(n\right)}\right\}$

이 때, $aS$의 모든 원소들은 $n$과 서로소인 수들끼리 곱한 수들이므로 그 원소들 역시 $n$과 서로소.

그리고 $aS$의 모든 원소는 $n$로 나눈 나머지가 서로 다르다 ($\because$ 만일 $ab_i \equiv ab_j (\text{mod}~n)$, $1 \leq i,j \leq \varphi \left(n \right)$인 서로 다른 정수 $i$, $j$가 존재한다면, $a(b_i - b_j )$가 $n$의 배수. $a$와 $n$이 서로소이므로 $b_i - b_j$가 $n$의 배수. 그런데, $b_i$와 $b_j$가 둘 다 $1$이상 $n$이하의 수들이므로 $-(n-1) \leq b_i -b_j \leq (n-1)$. 이 범위에는 $n$의 배수가 $0$뿐이므로 $b_i = b_j$. 즉, 모순)

그러므로 $aS$의 원소들을 $n$으로 나눈 나머지는 $S$의 원소들의 재배열이 된다.

따라서 $S$의 모든 원소의 곱과 $aS$의 모든 원소의 곱은 $n$으로 나눈 나머지가 같다.

$b_1\cdots b_{\varphi\left(n\right)} \equiv a^{\varphi\left(n\right)}b_1\cdots b_{\varphi\left(n\right)} \left(\text{mod} ~n\right)$

$\therefore ~ a^{ \varphi \left( n \right) } \equiv 1 \left( \text{mod}~ n \right)$

오일러 정리는 KMO 1차시험의 특성상 거듭제곱의 마지막 세 자리 수를 구하는 데 자주 사용된다. 예를 들어 $7^{2016}$의 마지막 세 자리 수를 구하고 싶을 때, $\varphi \left( 1000 \right) = 400$이므로 $7^{400} \equiv 1 \left(\text{mod}~1000 \right)$가 성립함을 이용하면, $7^{2016} \equiv \left( 7^{400} \right)^5 \times 7^{16} \left( \text{mod}~1000 \right)$에 의해 $7^{16}$을 $1000$으로 나눈 나머지를 구하면 된다.문제라면 그게 어려운 거지[2]

오일러 정리는 대표적인 공개키 암호화 방식 중 하나인 RSA의 가장 중요한 이론이 되는 정리다.
참고로 오일러 공식, 오일러 방정식과는 다른 것이다.

위의 정수론에 대한 정리와는 다른 정리이다. 내용은 다음과 같다.

함수 $f(x_k)$가 $x_k$에 대한 $n$차 동차함수이면, 다음이 성립한다.